{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Center of Star Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findCenter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出星型图的中心节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个无向的 <strong>星型</strong> 图，由 <code>n</code> 个编号从 <code>1</code> 到 <code>n</code> 的节点组成。星型图有一个 <strong>中心</strong> 节点，并且恰有 <code>n - 1</code> 条边将中心节点与其他每个节点连接起来。</p>\n",
    "\n",
    "<p>给你一个二维整数数组 <code>edges</code> ，其中 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> 表示在节点 <code>u<sub>i</sub></code> 和 <code>v<sub>i</sub></code> 之间存在一条边。请你找出并返回 <code>edges</code> 所表示星型图的中心节点。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/03/14/star_graph.png\" style=\"width: 331px; height: 321px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [[1,2],[2,3],[4,2]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [[1,2],[5,1],[1,3],[1,4]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 <= u<sub>i,</sub> v<sub>i</sub> <= n</code></li>\n",
    "\t<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>\n",
    "\t<li>题目数据给出的 <code>edges</code> 表示一个有效的星型图</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-center-of-star-graph](https://leetcode.cn/problems/find-center-of-star-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-center-of-star-graph](https://leetcode.cn/problems/find-center-of-star-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3],[4,2]]', '[[1,2],[5,1],[1,3],[1,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        if edges[1][0]==edges[0][0] or edges[1][1]==edges[0][0]:\n",
    "            return edges[0][0]\n",
    "        if edges[1][0]==edges[0][1] or edges[1][1]==edges[0][1]:\n",
    "            return edges[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        N = 0\n",
    "        for u, v in edges:\n",
    "            N = max(N, u, v)\n",
    "\n",
    "        D = [0 for _ in range(N+1)]\n",
    "        for u, v in edges:\n",
    "            D[u] += 1\n",
    "            D[v] += 1\n",
    "        for v in range(1, N+1):\n",
    "            if D[v] == N-1:\n",
    "                return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        x = edges[0][0]\n",
    "        y = edges[0][1]\n",
    "        n = len(edges)\n",
    "        flag1 = True\n",
    "        flag2 = True\n",
    "        for i in range(1,n):\n",
    "            if x not in edges[i]:\n",
    "                flag1 = False\n",
    "        for j in range(1,n):\n",
    "            if y not in edges[j]:\n",
    "                flag2 = False\n",
    "        if flag1:\n",
    "            return x\n",
    "        else:\n",
    "            return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        m = len(edges)\n",
    "        cnt = [0] * (m+2)\n",
    "        for u,v in edges:\n",
    "            cnt[u] += 1\n",
    "            cnt[v] += 1\n",
    "\n",
    "        \n",
    "        u, v in edges[-1]\n",
    "        if cnt[v] == m:\n",
    "            return v\n",
    "        if cnt[u] == m:\n",
    "            return u\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        degrees = [0] * (n + 1)\n",
    "        for x, y in edges:\n",
    "            degrees[x] += 1\n",
    "            degrees[y] += 1\n",
    "        for i, d in enumerate(degrees):\n",
    "            if d == n - 1:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        return edges[0][0] if edges[0][0] in (edges[1][0], edges[1][1]) else edges[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        nodes = []\n",
    "        for edge in edges:\n",
    "            if edge[0] in nodes:\n",
    "                return edge[0]\n",
    "            elif edge[1] in nodes:\n",
    "                return edge[1]\n",
    "            nodes.append(edge[0])\n",
    "            nodes.append(edge[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 2\n",
    "        bian = [0] * n\n",
    "        for ele in edges:\n",
    "            bian[ele[0]] += 1\n",
    "            bian[ele[1]] += 1\n",
    "        return bian.index(n - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        i, j = edges[0]\n",
    "        for vertex1, vertex2 in edges[1: ]:\n",
    "            if vertex1 == i or vertex1 == j:\n",
    "                return vertex1\n",
    "            else:\n",
    "                return vertex2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        return edges[0][0] if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1] else edges[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        adjacency = [0 for _ in range(n + 1)]\n",
    "        for i, j in edges:\n",
    "            adjacency[i] += 1\n",
    "            adjacency[j] += 1\n",
    "\n",
    "        for z in range(1, n + 1):\n",
    "            if adjacency[z] == n - 1:\n",
    "                return z\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        e1, e2 = edges[0], edges[1]\n",
    "        return collections.Counter([e1[0], e1[1], e2[0], e2[1]]).most_common(1)[0][0]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        a=[0 for i in range(len(edges)+1)]\n",
    "        for edge in edges:\n",
    "            a[edge[0]-1]+=1\n",
    "            a[edge[1]-1]+=1\n",
    "            if a[edge[0]-1]==len(edges):\n",
    "                return edge[0]\n",
    "            if a[edge[1]-1]==len(edges):\n",
    "                return edge[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        # 统计节点个数，点=边+1\n",
    "        n = len(edges)+1\n",
    "        #初始化每个点的度为0\n",
    "        degree = [0]*(n+1)  #### 由于节点从1开始，所以度0的索引用来占位，从1开始对应存储各个点的度数\n",
    "        for i,j in edges:\n",
    "            degree[i]+=1\n",
    "            degree[j]+=1\n",
    "        for i in degree:\n",
    "            if i >1:\n",
    "                return degree.index(i)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        sums = [0 for _ in range(n + 2)]\n",
    "        for edge in edges:\n",
    "            sums[edge[0]] += 1\n",
    "            sums[edge[1]] += 1\n",
    "        return sums.index(max(sums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        degrees = [0 for i in range(n + 1)]\n",
    "\n",
    "        for n1, n2 in edges:\n",
    "            degrees[n1] += 1\n",
    "            degrees[n2] += 1\n",
    "\n",
    "        for i, v in enumerate(degrees):\n",
    "            if v == n - 1:\n",
    "                return i\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)+1\n",
    "        degree=[0 for _ in range(n+1)]\n",
    "        for edge in edges:\n",
    "            degree[edge[0]]+=1\n",
    "            degree[edge[1]]+=1\n",
    "        for i in range(len(degree)):\n",
    "            if degree[i]==n-1:\n",
    "                return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        if edges[0][0] in edges[1]:\n",
    "            return edges[0][0]\n",
    "        else:\n",
    "            return edges[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "\n",
    "        degree=[[0,0] for i in range (len(edges)+1)]\n",
    "\n",
    "        for item in edges:\n",
    "\n",
    "            u,v=item[0]-1,item[1]-1\n",
    "\n",
    "            degree[u][0]+=1\n",
    "\n",
    "            degree[v][1]+=1\n",
    "\n",
    "        for i in range(len(edges)+1):\n",
    "\n",
    "            if degree[i][1]+degree[i][0]==len(edges):\n",
    "\n",
    "                return i+1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findCenter(self, edges: List[List[int]]) -> int:\n",
    "    s,s1,n = set(),0,len(edges)\n",
    "    for x,y in edges:\n",
    "      s1 += x+y\n",
    "      s.add(x)\n",
    "      s.add(y)\n",
    "    return (s1-sum(s))//(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        vetex = set()\n",
    "        for (v1, v2) in edges:\n",
    "            vetex.add(v1)\n",
    "            vetex.add(v2)\n",
    "        n = len(vetex)\n",
    "        degree = [0 for i in range(n+1)]\n",
    "        for (v1, v2) in edges:\n",
    "            degree[v1] += 1\n",
    "            degree[v2] += 1\n",
    "        \n",
    "        for v in range(len(degree)):\n",
    "            d = degree[v]\n",
    "            if d == n-1:\n",
    "                return v\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        lst = itertools.chain(*edges)\n",
    "        ctn = collections.Counter(lst)\n",
    "        for k, v in ctn.items():\n",
    "            if v == n:\n",
    "                return k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        inDegree = Counter(x for x, _ in edges)\n",
    "        outDegree = Counter(y for _, y in edges)\n",
    "        return next((i for i in range(len(edges) + 2) if inDegree[i] + outDegree[i] == len(edges)), -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        c = Counter(itertools.chain(*edges))\n",
    "        return c.most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        l1 = []\n",
    "        for i in edges:\n",
    "            l1.append(i[0])\n",
    "            l1.append(i[1])\n",
    "        s1 = set(l1)\n",
    "        l2 = [0 for _ in range(len(s1))]\n",
    "        for i in edges:\n",
    "            for j in range(2):\n",
    "                l2[i[j]-1] += 1\n",
    "        return(l2.index(max(l2))+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        inp = [0]*100000\n",
    "        out = [0]*100000\n",
    "        types = []\n",
    "        for a,b in edges:\n",
    "            types.append(a)\n",
    "            types.append(b)\n",
    "            inp[a-1] += 1\n",
    "            inp[b-1] += 1\n",
    "        length = len(set(types))\n",
    "        for i in range(length):\n",
    "            if inp[i] == length-1 :\n",
    "                return i+1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        #重复多次出现的\n",
    "        #arr = [x+y for x,y in edges]\n",
    "        return (sum([x+y for x,y in edges]) - sum(set([edges[i//2][i&1] for i in range(2*len(edges))])))//(len(edges)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        out = []\n",
    "        for i in edges:\n",
    "            out+=i\n",
    "\n",
    "        q = collections.Counter(out)\n",
    "\n",
    "        for i in q.keys():\n",
    "            if q[i]==len(edges):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        ans = []\n",
    "        for i in range(len(edges)):\n",
    "            for j in range (2):\n",
    "                ans.append(edges[i][j])\n",
    "        maxcount = Counter(ans).most_common(1)\n",
    "        return maxcount[0][0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        c = []\n",
    "        for e in edges:\n",
    "            c.append(e[0])\n",
    "            c.append(e[1])\n",
    "        cnt = collections.Counter(c)\n",
    "        return max(cnt, key=cnt.get)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        dp=[]\n",
    "        for i in edges:\n",
    "            dp.append(i[0])\n",
    "            dp.append(i[1])\n",
    "        import collections\n",
    "        c=collections.Counter(dp)\n",
    "        ans=0\n",
    "        tem=0\n",
    "        for i,j in c.items():\n",
    "            if j>tem:\n",
    "                tem=j\n",
    "                ans=i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        res = []\n",
    "        for item in edges:\n",
    "            res += item\n",
    "        return collections.Counter(res).most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        ans = []\n",
    "        for i in edges:\n",
    "            for j in i:\n",
    "                ans.append(j)\n",
    "        a = Counter(ans).most_common(1)\n",
    "        return a[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        from collections import Counter\n",
    "        temp = []\n",
    "        for edge in edges:\n",
    "            for j in edge:\n",
    "                temp.append(j)\n",
    "        cnt = Counter(temp)\n",
    "        for key,value in cnt.items():\n",
    "            if value == len(edges):\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        temp = []\n",
    "        for i in edges:\n",
    "            temp.append(i[0])\n",
    "            temp.append(i[1])\n",
    "        freq = Counter(temp)\n",
    "        for k,v in freq.items():\n",
    "            if v == len(edges): return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        res=[]\n",
    "        n=len(edges)\n",
    "        for i in range(n):\n",
    "            res+=edges[i]\n",
    "        num=Counter(res)\n",
    "        for i in range(1,n+2):\n",
    "            if num[i]==n:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        res=[]\n",
    "        n=len(edges)\n",
    "        for i in range(n):\n",
    "            res+=edges[i]\n",
    "        num=Counter(res)\n",
    "        for i in range(1,n+2):\n",
    "            if num[i]==n:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        from itertools import chain\n",
    "        from collections import Counter\n",
    "\n",
    "        array = list(chain(*edges))\n",
    "        n = max(array)\n",
    "        cnt = Counter(array)\n",
    "        for key, val in cnt.items():\n",
    "            if val == n - 1:\n",
    "                return key\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)\n",
    "        pointMap={}\n",
    "        for cur in edges:\n",
    "            pointMap[cur[0]]=pointMap.get(cur[0],0)+1\n",
    "            pointMap[cur[1]]=pointMap.get(cur[1],0)+1\n",
    "        for k,v in pointMap.items():\n",
    "            if v==n:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        cnt_dict = defaultdict(int)\n",
    "        for u, v in edges:\n",
    "            cnt_dict[u] += 1\n",
    "            cnt_dict[v] += 1\n",
    "        for i in range(n + 1):\n",
    "            if cnt_dict[i] == n - 1:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int: \n",
    "        d = defaultdict(int) \n",
    "        for a, b in edges: \n",
    "            d[a] +=1 \n",
    "            d[b] += 1 \n",
    "        for k, v in d.items(): \n",
    "            if v == len(edges): \n",
    "                return k \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        maxN = 0\n",
    "        ans = 0\n",
    "        tab = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            tab[a] += 1\n",
    "            if tab[a] > maxN:\n",
    "                ans = a\n",
    "                maxN = tab[a]\n",
    "            tab[b] += 1\n",
    "            if tab[b] > maxN:\n",
    "                ans = b\n",
    "                maxN = tab[b]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        note = {}\n",
    "        \n",
    "        for each in edges:\n",
    "            vertex1 = each[0]\n",
    "            vertex2 = each[1]\n",
    "            note[vertex1] = note[vertex1] + 1 if vertex1 in note else 1\n",
    "            note[vertex2] = note[vertex2] + 1 if vertex2 in note else 1\n",
    "\n",
    "        vertexNums = len(note)\n",
    "        for i in note:\n",
    "            if note[i] == vertexNums-1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        inMap = dict.fromkeys(range(1, n+1), 0)\n",
    "        for edge in edges:\n",
    "            inMap[edge[0]] = inMap[edge[0]] + 1\n",
    "            inMap[edge[1]] = inMap[edge[1]] + 1\n",
    "        \n",
    "        for (key, val) in inMap.items():\n",
    "            if val == n - 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        inMap = dict.fromkeys(range(1, n+1), 0)\n",
    "        for edge in edges:\n",
    "            inMap[edge[0]] = inMap[edge[0]] + 1\n",
    "            inMap[edge[1]] = inMap[edge[1]] + 1\n",
    "        \n",
    "        for (key, val) in inMap.items():\n",
    "            if val == n - 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        inrel = {key+1: 0 for key in range(len(edges)+1)}\n",
    "        #outrel = {key+1: 0 for key in range(len(edges)+1)}\n",
    "        for x, y in edges:\n",
    "            #outrel[x] += 1\n",
    "            inrel[x] += 1\n",
    "            inrel[y] += 1\n",
    "            #outrel[y] += 1\n",
    "        \n",
    "        for key, values in inrel.items():\n",
    "            #if values == len(edges) and outrel[key] == len(edges):\n",
    "            if values == len(edges):\n",
    "                return key\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)+1\n",
    "        graph = [[] for _ in range(len(edges)+2)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "            if len(graph[u]) == n-1:\n",
    "                return u\n",
    "            if len(graph[v]) == n-1:\n",
    "                return v\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        a = len(edges)\n",
    "        b = []\n",
    "        for i in range(a):\n",
    "            b.append(edges[i][0])  \n",
    "            b.append(edges[i][1])\n",
    "        print(b)\n",
    "        c = Counter(b)\n",
    "        for key , value in c.items():\n",
    "            if value == a:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        aes=list()\n",
    "        for c in edges:\n",
    "            for j in c:\n",
    "                aes.append(j)\n",
    "        print(aes)\n",
    "        c=collections.Counter(aes)\n",
    "        for k in c:\n",
    "            if c[k]==max(aes)-1:\n",
    "                return k\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in edges:\n",
    "            cnt[x] += 1\n",
    "            cnt[y] += 1\n",
    "        return max(cnt, key = lambda x: cnt[x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        deg = defaultdict(int)\n",
    "        for u, v in edges:\n",
    "            deg[u] += 1\n",
    "            deg[v] += 1\n",
    "        for u, d in deg.items():\n",
    "            if d != 1:\n",
    "                return u"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][0] not in dic:\n",
    "                dic[edges[i][0]] = 1\n",
    "            else:\n",
    "                dic[edges[i][0]] += 1\n",
    "            if edges[i][1] not in dic:\n",
    "                dic[edges[i][1]] = 1\n",
    "            else:\n",
    "                dic[edges[i][1]] += 1\n",
    "        for key in dic.keys():\n",
    "            if dic[key] == len(edges):\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        rd = Counter()\n",
    "        for x, y in edges:\n",
    "            rd[x] += 1\n",
    "            rd[y] += 1\n",
    "        return rd.most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        pointCnt = {}\n",
    "        for i in edges:\n",
    "            if i[0] in pointCnt:\n",
    "                pointCnt[i[0]] += 1\n",
    "            else:\n",
    "                pointCnt[i[0]] = 1\n",
    "            if i[1] in pointCnt:\n",
    "                pointCnt[i[1]] += 1\n",
    "            else:\n",
    "                pointCnt[i[1]] = 1\n",
    "        for k in pointCnt.items():\n",
    "            if k[1] == len(pointCnt) - 1:\n",
    "                return k[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        in_d = defaultdict(int)\n",
    "        for i in range(len(edges)):\n",
    "            in_d[edges[i][0]] += 1\n",
    "            in_d[edges[i][1]] += 1\n",
    "\n",
    "        n = 0\n",
    "        for i in range(len(edges)):\n",
    "            n = max(n,max(edges[i]))\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if in_d[i] == n-1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        n = len(edges)\n",
    "        ans = [0, 0]\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            j, k = edges[i]\n",
    "            if j not in dic:\n",
    "                dic[j] = 1\n",
    "            else:\n",
    "                dic[j] += 1\n",
    "            if k not in dic:\n",
    "                dic[k] = 1\n",
    "            else:\n",
    "                dic[k] += 1\n",
    "        for i in dic:\n",
    "            if dic[i] > ans[1]:\n",
    "                ans[1] = dic[i]\n",
    "                ans[0] = i\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        return collections.Counter(i for j in edges for i in j).most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        degree = {}\n",
    "        for edge in edges:\n",
    "            i = edge[0]\n",
    "            j = edge[1]\n",
    "            \n",
    "            if i in degree.keys():\n",
    "                degree[i]+=1 \n",
    "            else:\n",
    "                degree[i]=1\n",
    "\n",
    "            if j in degree.keys():\n",
    "                degree[j]+=1  \n",
    "            else:\n",
    "                degree[j]=1\n",
    "\n",
    "        for key, value in degree.items():\n",
    "            if value == len(degree)-1:\n",
    "                return key\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\r\n",
    "有一个无向的星型图\r\n",
    "由n个编号从1到n的节点组成\r\n",
    "星型图有一个中心节点\r\n",
    "并且恰有n-1条边将中心节点与其他每个节点连接起来\r\n",
    "给你一个二维整数数组edges\r\n",
    "其中edges[i] = [ui, vi]表示在节点 ui 和 vi 之间存在一条边\r\n",
    "请你找出并返回edges所表示星型图的中心节点\r\n",
    "'''\r\n",
    "\r\n",
    "'''\r\n",
    "对edges的每一个起始点和终止点进行储存,分别构建起始点数组和终止点数组\r\n",
    "count计数:出现n次的那个数字即中心节点\r\n",
    "'''\r\n",
    "class Solution:\r\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\r\n",
    "        n = len(edges)\r\n",
    "        starts = [0] * n\r\n",
    "        ends = [0] * n\r\n",
    "        for i in range(n):\r\n",
    "            starts[i] = edges[i][0]    # 储存全部起始节点\r\n",
    "            ends[i] = edges[i][1]      # 储存全部终止节点\r\n",
    "        # 对全部起始节点用count计数\r\n",
    "        countStarts = collections.Counter(starts)\r\n",
    "        # 对全部终止节点用count计数\r\n",
    "        countEnds = collections.Counter(ends)\r\n",
    "        # 对两组计数分别进行逆序排序\r\n",
    "        countStarts = sorted(countStarts.items(), key=lambda x:x[1], reverse=True) \r\n",
    "        # key=lambda x:x[1]表示按照countStarts的值进行排序，reverse=True表示逆序\r\n",
    "        countEnds = sorted(countEnds.items(), key=lambda x:x[1], reverse=True)\r\n",
    "        # 将countStarts和countEnds中第一个元素的value进行比较\r\n",
    "        max = countStarts[0][1] if countStarts[0][1] > countEnds[0][1] else countEnds[0][1]\r\n",
    "        # 返回max对应的key\r\n",
    "        return countStarts[0][0] if countStarts[0][1] == max else countEnds[0][0]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "\n",
    "        for x , y in edges : \n",
    "            if x in dic :\n",
    "                dic[x] += 1\n",
    "            else:\n",
    "                dic[x] =1 \n",
    "            \n",
    "            if y in dic :\n",
    "                dic[y] += 1\n",
    "            else:\n",
    "                dic[y] =1 \n",
    "        \n",
    "        dic = sorted(dic.items() , key = lambda x : x[1])\n",
    "        #print(dic)\n",
    "        return dic[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges) :   \n",
    "        \"\"\"\n",
    "        输出出现次数最多的结点\n",
    "        \"\"\"\n",
    "        s = Counter([x for i in edges for x in i])\n",
    "        max_count = max(s.values())\n",
    "\n",
    "        return [key for key,value in s.items() if value==max_count][0]\n",
    "        \n",
    "\n",
    "s= Solution()\n",
    "s.findCenter([[1,2],[5,1],[1,3],[1,4]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        redict = defaultdict(int)\n",
    "        for i in edges:\n",
    "            a, b = i[0], i[1]\n",
    "            redict[a] += 1\n",
    "            redict[b] += 1\n",
    "        tmp_val = 0\n",
    "        tmp_key = 0\n",
    "        print(redict)\n",
    "        for k,v in redict.items():\n",
    "            if v > tmp_val:\n",
    "                tmp_key = k\n",
    "                tmp_val = v\n",
    "\n",
    "        return tmp_key\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        counter = Counter([x for x, _ in edges] + [y for _, y in edges])\n",
    "        return counter.most_common()[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        counter = Counter([x for x, _ in edges] + [y for _, y in edges])\n",
    "        return counter.most_common()[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        s = {}\n",
    "        for dp in edges:\n",
    "            if dp[0] not in s:\n",
    "                s[dp[0]] = 0\n",
    "            if dp[0] in s:\n",
    "                s[dp[0]] += 1\n",
    "            if dp[1] not in s:\n",
    "                s[dp[1]] = 0\n",
    "            if dp[1] in s:\n",
    "                s[dp[1]] += 1\n",
    "        f = sorted(s.items(), key=lambda x: x[1])\n",
    "        return f[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        ans1={}\n",
    "        ans2={}\n",
    "        for nums in edges:\n",
    "            ans1[str(nums[0])]=ans1.get(str(nums[0]),0)+1\n",
    "            ans2[str(nums[1])]=ans2.get(str(nums[1]),0)+1\n",
    "        for nums in ans1:\n",
    "            if ans1[nums]>1:\n",
    "                return int(nums)\n",
    "        for nums in ans2:\n",
    "            if ans2[nums]>1:\n",
    "                return int(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        ans = []\n",
    "        for i in edges:\n",
    "            ans.extend(i)\n",
    "        ans = dict(collections.Counter(ans))\n",
    "        for i in ans.items():\n",
    "            if i[1]==len(edges):\n",
    "                return i[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        ans1={}\n",
    "        ans2={}\n",
    "        for nums in edges:\n",
    "            ans1[str(nums[0])]=ans1.get(str(nums[0]),0)+1\n",
    "            ans2[str(nums[1])]=ans2.get(str(nums[1]),0)+1\n",
    "        for nums in ans1:\n",
    "            if ans1[nums]>1:\n",
    "                return int(nums)\n",
    "        for nums in ans2:\n",
    "            if ans2[nums]>1:\n",
    "                return int(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        list1 = []\n",
    "        for item in edges:\n",
    "            for iii in item:\n",
    "                list1.append(iii)\n",
    "        count = Counter(list1)\n",
    "        count1 = dict(count)\n",
    "        if max(count1.values()) == len(edges):\n",
    "            for item in count1:\n",
    "                if count1[item] == max(count1.values()):\n",
    "                    return item\n",
    "        else:return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        return Counter(list(chain(*edges))).most_common()[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        degree = { }\n",
    "        res=0\n",
    "        for x,y in edges:\n",
    "            degree[y]=degree.get(y,0)+1\n",
    "            degree[x]=degree.get(x,0)+1\n",
    "            \n",
    "        return sorted(list(degree.items()),key=lambda x:x[1])[-1][0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v)\n",
    "            g[v-1].append(u)\n",
    "        for ix,i in enumerate(g):\n",
    "            if len(i) == 1:\n",
    "                return i[0]\n",
    "            else:\n",
    "                return ix+1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        d = {}\n",
    "        for i in range(len(edges)):\n",
    "            for j in range(2):\n",
    "                if edges[i][j] not in d:\n",
    "                    d[edges[i][j]] = 1\n",
    "                else:\n",
    "                    d[edges[i][j]] += 1\n",
    "        \n",
    "        ls = sorted(list(d.items()), key=lambda x: x[1], reverse=True)\n",
    "        return ls[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "      num_list = []\n",
    "      for i in edges:\n",
    "        for j in range(2):\n",
    "         num_list.append(i[j])\n",
    "      count_dict = {}\n",
    "      for num in num_list:\n",
    "        if num in count_dict:\n",
    "          count_dict[num] += 1\n",
    "        else: count_dict[num] = 1\n",
    "      max_count = max(count_dict.values())\n",
    "      for key, value in count_dict.items():\n",
    "        if value == max_count:\n",
    "          most_common_values = key\n",
    "      if max_count == len(edges):\n",
    "        return most_common_values\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCenter(self, edges: List[List[int]]) -> int:\n",
    "        n = []\n",
    "        for x,y in edges:\n",
    "            n.append(x)\n",
    "            n.append(y)\n",
    "        return Counter(n).most_common(1)[0][0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
